package org.leetcode.middle.leetcode279;

import java.util.Arrays;

public class Solution {

    public int numSquares5(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        dp[1] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                if (dp[j-i*i]!=Integer.MAX_VALUE){
                    dp[j]=Math.min(dp[j],dp[j-i*i]+1);
                }
            }
        }

        return dp[n];
    }

    public int numSquares3(int n) {

        int[] dp = new int[n + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }

        return dp[n];
    }

    public int numSquares2(int n) {

        int[] dp = new int[n + 1];

        for (int i = 0; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }

    public int numSquares(int n) {

        int[] dp = new int[n + 1];

        //dp[5]的含义：容量为5时，得到的完全平方数和最小值
        for (int j = 0; j < dp.length; j++) {
            dp[j] = Integer.MAX_VALUE;
        }

        dp[0] = 0;

        //i表示平方和，2表示2*2，3表示3*3
        for (int i = 1; i <= n; i++) {
            //j表示背包大小，j从i*i开始遍历的原因：如果j<i*i,i*i会无法构成j
            for (int j = i * i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        solution.numSquares(3);
    }
}
